정보과학회논문지 (Journal of KIISE)
Current Result Document : 3 / 28
이전건
다음건 
| 한글제목(Korean Title) |
사각망 순열패턴매칭 문제에 대한 병렬알고리즘 |
| 영문제목(English Title) |
Parallel Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem |
| 저자(Author) |
최지효
김영호
나중채
심정섭
Jihyo Choi
Youngho Kim
Joong Chae Na
Jeong Seop Sim
|
| 원문수록처(Citation) |
VOL 46 NO. 04 PP. 0299 ~ 0307 (2019. 04) |
한글내용
(Korean Abstract) |
사각망 순열패턴매칭은 텍스트 T(|T|=n) 와 패턴 P(|P|=m)가 주어졌을 때, P와 순위동형인 T의 모든 사각망 부분서열을 찾는 문제이다. 본 논문에서는 사각망 순열패턴매칭문제를 해결하는 두 가지 병렬알고리즘을 제시한다. 먼저 O(n)개의 스레드를 사용하여 O(nm)시간에 해결하는 병렬알고리즘을 제시한 후, O(nm)개의 스레드를 사용하여 O(n)시간에 해결하는 병렬알고리즘을 제시한다. 다우존스 지수 데이터에 대한 실험결과, n=36,364, m=30일 때, 순위통계트리를 사용한 순차알고리즘에 비해 첫번째 병렬알고리즘은 약 7.2배 빠른 수행시간을 보였고, 두 번째 병렬알고리즘은 약 20.6배 빠른 수행시간을 보였다.
|
영문내용
(English Abstract) |
Given a text T(|T|=n) and a pattern P(|P|=m), the boxed-mesh permutation pattern matching problem asks to find all boxed subsequences of T that are order-isomorphic to P. In this paper we present two parallel algorithms for the problem. We first propose an O(nm)-time parallel algorithm using O(n)threads and then propose an O(n)-time algorithm using O(nm)threads. The experimental results for Daw Jones Industrial Average show that our first and second algorithms run approximately 7.2 times and 20.6 times, respectively, faster compared to the sequential algorithm using order-statistics trees when n=36,364 and m=30.
|
| 키워드(Keyword) |
순위동형
사각망 순열패턴매칭
병렬알고리즘
스레드
order-isomorphism
boxed-mesh permutation pattern matching
parallel algorithm
thread
|
| 파일첨부 |
PDF 다운로드
|
